package evaluation;

import java.util.HashMap;

/**
 * 单向随机链表的的复制，通过hash表来解决问题,也可以不通过hash表来解决
 */
public class CopyLinkWithRand {


    //哈希表解决问题
    public static Node CopyLinkWithRand(Node head){
        HashMap<Node,Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null){
            map.put(cur,new Node(cur.Data));
            cur = cur.Next;
        }
        cur = head;
        while (cur !=null){
            map.get(cur).Next = map.get(cur.Next);
            map.get(cur).rand = map.get(cur.rand);
            cur = cur.Next;
        }
        return map.get(head);
    }

    public static Node CopyLinkWithRand2(Node head){
        if (head == null){
            return null;
        }
        Node cur = head;
        Node next = null;
        while (cur !=null){
            next = cur.Next;
            cur.Next = new Node(cur.Data);
            cur.Next.Next = next;
            cur = next;
        }
        cur = head;
        Node curCopy = null;
        while (cur!=null){
            next = cur.Next.Next;
            curCopy = cur.Next;
            curCopy.rand = cur.rand != null ? cur.rand.Next : null;
            cur = next;
        }
        Node res = head.Next;
        cur = head;
        //split
        while (cur != null){
            next = cur.Next.Next;
            curCopy = cur.Next;
            cur.Next = next;
            curCopy.Next = next != null ? next.Next : null ;
            cur = next;
        }
        return res;
    }


    static class Node {
        private int Data;// 数据域
        private Node Next;// 指针域
        private Node rand;// 随机指针域
        public Node(int Data) {
            // super();
            this.Data = Data;
        }
        public int getData() {
            return Data;
        }
        public void setData(int Data) {
            this.Data = Data;
        }

        public Node getNext() {
            return Next;
        }
        public void setNext(Node Next) {
            this.Next = Next;
        }
    }
}
